package Tree;

import java.util.Arrays;

public class LCA1 {

    public static int MAXN = 50_0001;

    public static int LIMIT = 20;

    public static int power;

    /**
     * @param n 正数
     * @return 不大于n的最大的2的倍数
     */
    public static int log2(int n) {
        int ans = 0;
        while ((1 << ans) <= (n >> 1)) {
            ans++;
        }
        return ans;
    }

    public static int[] head = new int[MAXN];

    // 无向边的树，最多 2 * (n-1)条边 < 2 * n,保证装的下
    public static int[] next = new int[MAXN << 1];

    public static int[] to = new int[MAXN << 1];

    public static int cnt;

    public static int[] deep = new int[MAXN];

    // stjump[i][p]: 节点i向上跳2^p步，到达的节点编号
    public static int[][] stjump = new int[MAXN][LIMIT];

    public static void build(int n) {
        // 计算跳的最大层数
        power = log2(n);
        // 初始的边号
        cnt = 1;
        Arrays.fill(head, 1, n + 1, 0);
    }

    public static void addEdge(int u, int v) {
        // 当前边的下一条边指向上一条边
        next[cnt] = head[u];
        // 记录当前边到的点v
        to[cnt] = v;
        // 更新u点出发的第一条边号
        head[u] = cnt++;
    }

    public static void dfs(int u, int f) {
        // 当前节点的深度 = 父节点深度 + 1
        deep[u] = deep[f] + 1;
        // 当前节点向上跳一层到 父节点(f)
        stjump[u][0] = f;
        // 跳出条件：跳的层数2^p > 当前节点的长度
        for (int p = 1; (1 << p) <= deep[u]; p++) {
            stjump[u][p] = stjump[stjump[u][p - 1]][p - 1];
        }

        for (int e = head[u]; e != 0; e = next[e]) {
            if (to[e] != f) {
                dfs(to[e], u);
            }
        }
    }

    public static int lca(int a,int b) {
        // 保证a的深度大于b
        if (deep[a] < deep[b]) {
            int tmp = a;
            a = b;
            b = tmp;
        }
        // a节点向上跳到 b节点所在的深度
        for (int p = power;p>=0;p--) {
            if (deep[stjump[a][p]] >= deep[b]) {
                a = stjump[a][p];
            }
        }

        if (a == b) {
            // b节点就是最近公共祖先，over
            return a;
        }

        // a,b两个节点深度一样了，开始以前向上跳
        for (int p = power; p >= 0; p--) {
            // 检查跳过去之后，是否跳到同一个祖先节点，如果是就不能跳
            if (stjump[a][p] != stjump[b][p]) {
                a = stjump[a][p];
                b = stjump[b][p];
            }
        }

        // 在向上跳2^0层就是最近公共祖先
        return stjump[a][0];
    }
}
